package cn.fxzhang.leetcode.no00;

/**
 * 80. 删除有序数组中的重复项 II
 * 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
 * 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
 * 0 <= nums.length <= 3 * 104
 * -10^4 <= nums[i] <= 10^4
 * nums 已按升序排列
 *
 * 类型：数组/指针
 * 题解：双指针，1个记录判断的位置，1个记录存放的位置
 * 时间复杂度：O(N), N是数组中的元素数量
 * 空间复杂度：O(1)
 *
 * 提交记录(1/1)：
 * 执行用时: 0 ms, 击败了100.00%
 * 内存消耗: 38.5 MB, 击败了79.19%
 *
 * 【中等】通过次数99,127提交次数166,376
 * @author 张晓帆
 * @date 2021/4/6
 */
public class P0080_Remove_Duplicates_From_Sorted_Array_Ii {

    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (nums.length <= 2){
            return len;
        }
        int k = 1;
        for (int i=2; i<len; i++){
            if (nums[i] != nums[k-1]){
                nums[++k] = nums[i];
            }
        }
        return k+1;
    }
}
